package leetcode_day._2021._202110;

/**
 * @author yzh
 * @version 1.0
 * @date 2021/10/25 9:02
 * 搜索二维矩阵 II
 * 编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：
 * 每行的元素从左到右升序排列。
 * 每列的元素从上到下升序排列。
 * 算法：二叉搜索树
 * 这样的矩阵从右上角开始看，就是一颗二叉树，而且是二叉搜索树
 * 从右上角开始遍历
 */
public class _25_240 {
    public static void main(String[] args) {
        int[][] matrix = {{1, 4, 7, 11, 15}, {2, 5, 8, 12, 19}, {3, 6, 9, 16, 22},
                {10, 13, 14, 17, 24}, {18, 21, 23, 26, 30}};
        System.out.println(new _25_240().searchMatrix(matrix, 5));
    }

    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0) return false;
        int m = matrix.length, n = matrix[0].length;
        int r = 0, c = n - 1;
        while (r < m && c >= 0) {
            int now = matrix[r][c];
            if (now == target) return true;
            else if (now < target) ++r;
            else --c;
        }
        return false;
    }

}
